package com.wyw.learning.offer;

/**
 * 数组中重复数据
 *      也可以先排序
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/17 9:57
 */
public class Offer003 {

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,0,2,3,5};
        findRepeatNumber(nums);
    }

    // 借助哈希表
//    public static int findRepeatNumber(int[] nums) {
//        HashMap<Integer, Integer> map = new HashMap<>();
//
//        for(int i : nums) {
//            if(map.get(i) != null)
//                return i;
//            map.put(i,i);
//        }
//
//        return -1;
//    }

    // 利用set的特性
//    public static int findRepeatNumber(int[] nums) {
//
//        HashSet<Integer> set = new HashSet();
//        for(int i: nums) {
//            if(!set.add(i))
//                return i;
//        }
//        return -1;
//    }

//    public static int findRepeatNumber(int[] nums) {
//
//        int i = 0;
//        while (i < nums.length) {
//            if (nums[i] == i) {
//                i++;
//                continue;
//            }
//
//            if (nums[nums[i]] == nums[i]) return nums[i];
//
//            int t = nums[nums[i]];
//            nums[nums[i]] = nums[i];
//            nums[i] = t;
//        }
//        return -1;
//    }

    public static int findRepeatNumber(int[] nums) {

        int[] arr = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            arr[nums[i]]++;
            if(arr[nums[i]] > 1) return nums[i];
        }
        return -1;
    }
}

